A compiler is a program that translates programs written in a source language to a those written in a target language. The source language is often a high level language such as Fortran. The target language is often assembly code or machine language, but may be a higher level language as well. A compiler usually performs optimizations to improve the performance of the target program for the given machine. An optimization is any transformation of the program with the aim of improving the performance of the target program.
To perform these tasks, often compilers comprise a front end, an intermediate language, an optimizer and a back end. The front end is designed to translate a specific high level language or languages (input program) into an intermediate representation of the program called the intermediate language (IL) or intermediate form. The intermediate language is distinct from the input or output program. The intermediate language is designed to be operated on by the specific optimizer of the compiler. The optimizer operates on the intermediate language by passing through the intermediate form a given number of times. During each pass through the intermediate form, the optimizer changes (translates) the intermediate form to an intermediate form which ultimately can be translated by the back end into a more efficient target language program for the target computer. Some compilers, i.e., the optimizers of the compilers, generate several levels of intermediate language. When the optimizer has completed its optimization of the final intermediate language, the back end of the compiler converts the final intermediate language into the target language of the compiler. Typically, this is machine executable object code that will be executed by the computer.
Optimizers include the methods to optimize the intermediate form into the most efficient target within the capability of the compiler. Accordingly, the optimizer is much harder to design and develop and has a great deal more complexity and code than either the front or back end of the compiler. As a result, compiler front ends are often redesigned for each high level language to produce an intermediate language (IL) that is compatible with a specific compiler optimizer to avoid redesigning the optimizer. Because the front end can be adapted relatively inexpensively to different high level languages, the compiler IL and optimizer are essentially high level (source language) independent.
Data movement refers to the transfer of values between devices. A device is a component, or logical group of components, of a computer. Devices are classified as either active or passive. Active devices are those for which the compiler has to explicitly generate code to be executed (e.g., processors, controllers, etc.). Passive devices are those for which no explicit code needs to be generated, because they have associated hardware to automatically service requests (e.g., cache, memory, etc.).
Although the prior art compilers insert instructions into the IL during optimization for the transfer of data between devices, these transfer instructions are only either implicit or explicitly target machine dependent. Examples of implicit transfers are usage of reads or writes to variables in the IL, and the target computer is a virtual shared-memory parallel computer: each read or write could result in data movement from one processor's local memory to another if the referenced variable was not available locally. Examples of machine dependent explicit transfers are the usage of matching send and receive operations during compiler optimization, and the target computer is a message-passing distributed-memory parallel computer: send and receive primitives are provided by the target computer as the only mechanism for specifying data movement between processors. The problem with implicit data transfers is that they are not explicitly represented in the IL and hence their optimization is not possible at compile-time, thus limiting the capability and flexibility of the compiler. On the other hand, the problem with machine dependent explicit data transfer operations in the IL is that the compiler optimizer design becomes very specific to the data movement mechanisms supported on a particular target computer. In summary, prior art optimizers either do not represent data movement and placement as an operation in the intermediate form (i.e. they are implicit) or they represent it explicitly in a machine-dependent way.
Prior art compilers also partition data, in particular, those that use the SPMD model. Partitioning refers to the distribution of data values among various devices. These initial data placements can either be specified in a high-level language, such as High Performance Fortran, or inserted by the optimizer. A device is said to own the data which is in a partition assigned to the device. For example, each processor device in a distributed memory machine or specific levels of memory in a memory hierarchy (such as a cache device and a memory device) will own the data values in the partition assigned to that respective device. Prior art compilers do allow for the possibility of implicitly transferring data between processors during the computation; this implies a corresponding change in what the processors own. However, in prior art compilers, the ownership transfer operation was not a separate operation from the data transfer operation in the IL, and consequently, could not be separately manipulated and optimized by the compiler.